\section{Message Authentication Codes }

\subsection{4.5 CBC-MAC}
\frame{
  \frametitle{4.5 CBC-MAC}
  \begin{itemize}
      \item A principio, MACs podem ser construidas apartir de  cifras de blocos. \\
     \vfill
      \item Entretanto a construção resultante é bastante ineficiente: para se calcular uma MAC tag numa mensagem de tamanho $l \centerdot n$ é necessario aplicar a cifra de bloco $4l$ vezes e a MAC tag seria de  $(4l + 1)n$ bits\\ 
      \vfill
      \item Felizmente é possivel alcançar soluções mais eficientes. \\
     \vfill
      \item O CBC-MAC é similiar ao ao modo de criptação CBC e é amplamente usado na prática.\\ 
      \vfill
     \end{itemize}
}

\frame{
  \frametitle{4.5 CBC-MAC}
  \begin{itemize}
      \item Primeiro a mensagem é quebrada em blocos e a cifra de bloco é aplicada.\\
\vfill
\item Entretanto só é necessario aplicar a cifra de bloco $l$ vezes para calcular  a tag de uma mensagem de tamanho $l \centerdot n$ onde $n$ é o tamanho do bloco da mensagem.\\
     \vfill
      \item Com isso a MAC tag tem somente $l$ bits (i.e., um único bloco).\\ 
      \vfill
     \end{itemize}
}

\frame{
  \frametitle{4.5 CBC-MAC}

	\begin{block}{Construction 4.9}
		Let $F$ be a pseudorandom function, and fix a length function$l$. The basic CBC-MAC construction is as follows:

  \begin{itemize}
	\item $Gen:$ on input $1{n}$, choose $k \leftarrow \{0,1\}^{n}$ uniformly at random.\\
	\vfill
	\item $Mac:$ on input a key $k \in \{0,1\}^{n}$ and a message $m$ of length $l(n) \centerdot n$, do the following ( we set $l = l(n)$ in what follows): 
	\vfill
	\begin{enumerate}
		\item Parse $m$ as $ m = m_{1}, . . . , m_{l}$ where each $m_{i}$ is of lenght $n$, and set $t_{0} := 0^{n}$.\\
		\vfill
		\item For $i = 1$ to $l$, set $t_{i} := F_{k}(t_{i-1} \oplus m_{i})$.\\
	\end{enumerate}
     \end{itemize}
	Output $t_{l}$ as the tag.
	\begin{itemize}
		\item Vrfy: on input a key $k \in \{0,1\}^{n}$, a message $m$ of lenght $l(n) \centerdot n$, and a tag$t$ of length $n$, output 					$1$ if and only if $t ={?} Mac_{k}(m)$.
	\end{itemize}
	\end{block}
	\center CBC-MAC for fixed-length messages.\\

}

\frame{
  \frametitle{4.5 CBC-MAC}
  \begin{itemize}
      \item A construção é descrita para mensagems de tamanho multiplos de $n$, mas é possivel lidar com mensagens de tamanho arbitrario (mas fixo) usando padding.\\
     \vfill
	\begin{block}{Theorem 4.10}
		Let $l$ be a polynomial. If $F$ is a pseudorandom function, then \textit{Construction 4.9} is a fixed-length MAC for messages of 				length $l(n) \centerdot n$ that is existentiallly unforgeable under an adaptive chosen-message attack.
	\end{block}
     \vfill
	\item Vale ressaltar que a construção somente é segura quando o tamanho da menssagem que está sendo autenticada é fixo.\\
     \vfill
     \end{itemize}
}

\frame{
  \frametitle{CBC-MAC vs. CBC-mode encryption.}
  \begin{itemize}
      \item Existem duas diferenças entre o CBC-MAC e o  CBC-mode: \\
     \vfill
	\begin{enumerate}
		\item CBC-mode encryption usa um $IV$ randomico e isso é crucial para se obter segurança. Em contraste, CBC-MAC não usa um $IV$ e isso tambem é crucial para se obter segurança. No caso, Usar um $IV$ randomico no CBC-MAC não é seguro.\\
	\vfill
	\item No CBC-mode todos os lbocoks $t_{i}$ são retornados pelo algoritmo de criptação como parte do texto cifrado, enquanto no CBC-MAC somente o ultimo bloco é retornado. Isso acontece porque no 1o caso todos os blocos são necessarios para que a decriptação seja possivel, enquanto no 2o caso isso não é necessario.
	\end{enumerate}
      \vfill
     \end{itemize}
}

\frame{
  \frametitle{CBC-MAC for variable-length messages.}
  \begin{itemize}
      \item Para se conseguir segurança para mensagens de tamanho variado, algumas modificações precisam ser feitas na \textit{Contrução 4.9}. Três possiveis opções que podem ser provadas seguras são: \\
     \vfill
	\begin{enumerate}
		\item Aplicar uma função pseudorandomica  (cifra de bloco) ao tamanho $l$ da mensagem de entrada, afim de se obter uma chave 				$k_{l}$ (i.e., definindo $k_{l}$). Depois calcula-se o CBC-MAC usando a chave $k_{l}$. Isso garante que chaves diferentes vão 			ser usadas para autenticar mensagens de tamanhos diferentes.\\
\vfill
		\item Anexar ao começo da nensagem o tamanho $|m|$ ( codificada com uma string de n-bit), e então calcular o CBC-MAC na 					mensagem resultante. Entretanto, anexar a o tamanho do bloco no final da mensagem não é seguro.\\
	\vfill
	\item Mudar o esquema para que a geração de chaves escolha duas chaves diferentes $k_{1} \leftarrow \{1,0\}^{n}$ e $k_{2} 					\leftarrow \{1,0\}^{n}$, Então, para aytebtucar a mensagem $m$ primeiro se calcula o CBC-MAC de $m$ usando $k_{1}$, com 				$t$ sendo o resultado; retorna-se a tag $\hat{t} := F_{k_{2}}(t)$.\\
	\end{enumerate}
      \vfill
     \end{itemize}
}


\frame{
  \frametitle{CBC-MAC for variable-length messages.}
  \begin{itemize}
      \item A terceira opçãp tem a vantagem que não é necessario saber o tamanho da mensagem antes de começar a calcular o MAC. Entretanto essa abordagem precisa de duas chaves. Uma saida é guardar uma única chave $k$ edepois derivar $k_{1} = F_{k}(1)$  e $k_{2} = F_{k}(2)$  no começo do calculo.
\vfill
\item Entretanto só é necessario aplicar a cifra de bloco $l$ vezes para calcular  a tag de uma mensagem de tamanho $l \centerdot n$ onde $n$ é o tamanho do bloco da mensagem.\\
     \vfill
      \item Com isso a MAC tag tem somente $l$ bits (i.e., um único bloco).\\ 
      \vfill
     \end{itemize}
}


\subsection{4.6 Collision-Resistant Hash Functions}

\frame{
  \frametitle{4.6 Collision-Resistant Hash Functions}
  \begin{itemize}
      \item Funções hash são fuções que pegam uma string de tamanho arbitrario e comprimem-nas em strings menores.\\
\vfill
\item É usada em estrutura de dados para guardar um conjunto de elementos.\\
     \vfill
      \item Boas funções hash tem tão poucas colisões quanto possivel, espalhando adequadamente seus elementos pela função\\ 
      \vfill
      \item Funções hash resistentes a colisão requerem veementemente que as colisões sejam minimas.\\ 
      \vfill
      \item Ainda, na criptografia um adversario pode causar colisões enquanto na estrutura de dados essa intenção não existe.\\ 
      \vfill
     \end{itemize}
}


\frame{
  \frametitle{4.6.1 Defining Collision Resistance}
  \begin{itemize}
	\item Uma \textit{collisão} em uma função $H$ é um par de entradas $x$ e $x'$ tal que $H(x) = H(x')$. E uma função é resistente a colisões se é inviavel com qualquer algoritimo PPT encontrar uma colisão em H.\\
	\vfill
	\item As funções tem dominio infiito ( qualquer tamanho de mensagem) e um intervalo finito. Assim sempre existirá uma colisão e portanto só é necessario que seja dificil encontrar uma colisão\\ 
	\vfill
	\item Existe uma familia de funções hash que são indexadas por uma chave $s$, definida por $H{s}(x) \doteq H(s,x)$. O prerequisito é que seja dificil para se encontrar uma colisão em $H^{s}$ para um s gerado randomicamente.\\ 
	\vfill
	\item Podem existir chaves que não mapeiam $H^{s}$ e portanto será usado um $Gen$ em vez de s ser escolhido ao acaso. Alem, chave $k$ não é secreta, por isso $H^{s}$ e não $H_{s}$\\ 
	\vfill
	\end{itemize}
}

\frame{
  \frametitle{4.6 Collision-Resistant Hash Functions}
	\begin{block}{Definition 4.11}
		A hash function is a pair of probabilistic polynomial-time algorithms ($Gen$,$H$) satisfaying the following:
		\begin{itemize}
			\item $Gen$ is a probabilistic algorithm which takes as input a security parameter $1^{n}$ and outputs a key $s$. We assume that $1^{n}$ is implicit in $s$.\\
			\vfill
			\item There existis a polynomial $l$ such taht $H$ takes as input a key $s$ and a string $x \in \{0,1\}*$ and outputs a string $H^{s}(x) \in \{0,1\}^{l(n)}$ (where $n$ is the value of the security parameter implicity in $s$).\\ 
			\vfill	
		\end{itemize}
	\end{block}
  \begin{itemize}
		\item Se $H^{s}$ é definido para entradas $x \in \{0,1\}^{l'(n)}$ e $l'(n) > l(n)$, então dizemos que $(Gen,H)$ é uma função has de tamanho fixo para entradas de tamanho $l'(n)$.
	\vfill
	\end{itemize}
}


\frame{
  \frametitle{The colision-fiding experiment $Hash-coll_{\mathcal{A},\Pi}(n)$ }
	\begin{block}{The colision-fiding experiment $Hash-coll_{\mathcal{A},\Pi}(n)$}
	\begin{enumerate}
		\item A key $s$ is generated by running $Gen(1^n ) $.\\
		\vfill
		\item The adversary $\mathcal{A}$ is given $s$ and outputs $x$, $x'$. (If $\Pi$ is a fixed-lenght hash function for inputs of length $l'(n)$ then we require $x, x' \in \{0,1\}^{l(n)}$.)\\
		\vfill
		\item The output of the experiment is defined to be $1$ if and only if $x \neq x'$ and $H^{s}(x) = H^{s}(x')$. In such a case we say that $\mathcal{A}$ has found a collision.\\
		\vfill
		\end{enumerate}
	\end{block}

	\begin{itemize}
	\item  Assim, nenhum adversario consegue achar uma colisão a não ser com probabilidade desprezivel.\\
	\vfill
	\end{itemize}
}

\frame{
  \frametitle{4.6 Collision-Resistant Hash Functions}
	\begin{block}{Definition 4.12}
		A hash function $\Pi = (Gen,H)$ is collision resistant if for all PPT adversaries $\mathcal{A}$ there exists a negligible function $negl$ such that
		\begin{equation}
			\Pr[Hash-coll_{\mathcal{A},\Pi}(n) = 1] \leq negl(n).
		\end{equation}
	\end{block}
}

\frame{
  \frametitle{4.6.2 Weaker Notions of Security for Hash Functions}
  \begin{itemize}
	\item Ao se considerar funções hash criptograficas, existem tres tipicos niveis de segurança a serem considerados:.\\
	\vfill
	\begin{enumerate}
		\item \textit{Collision resistance:} This is the stronguest notion and the one we have considered so far.\\
		\vfill
		\item \textit{Second pre-image resistance:} Given $s$ and $x$ it is infeasible for a PPT adversary to find $x' \neq x$ such taht $H^{s}(x') = H^{s}(x)$.\\ 
		\vfill
		\item \textit{Pre-image resistance:} Given $s$ and $y = H^{s}(x)$ (but not $x$ itself) for a randomly-chosen $x$, it is infeasible for a PPT adversary to find a value $x'$ such tat $H^{s}(x') = y$.\\ 
		\vfill
	\end{enumerate}
	\end{itemize}
}
\frame{
  \frametitle{4.6.2 Weaker Notions of Security for Hash Functions}
  \begin{itemize}
	\item Qualquer função hash resistente a colisão tanbem é second pre-image resistente. Isso porque se dado um $x$ o adversário pode achar $x' \neq x$ para qual $H^{s}(x') = H^{s}(x)$ então ele pode encontrar um par $x$ e $x'$ qualquer.\\
	\vfill
	\item Da mesma forma, qualquer função hash que é second pre-image resistente tambem é pre-image resistente. Se for possivel inverter $y$ e conseguir um $x'$ tal que $H^{s}(x') = y$, então seria possivel pegar uma dada entrada $x$ , calcular $y := H^{s}(x)$, e então inverter $y$ para se obter $x'$.\\ 
	\vfill
	\end{itemize}
}

\frame{
  \frametitle{4.6.3 A Generic "Birthday" Attack}
  \begin{itemize}
	\item O ataque funciona assim: Escolhe-se $q$ entradas distintas arbritarias $x_{1}, . . . , x_{q} \in \{0,1\}^{2l}$, computa-se $y_{i} := H(x_{i})$, e testa-se se qualquer dois valores $y_{i}$ são iguais.\\
	\vfill
	\item Considerando $H$ uma função ideal randomica, podemos resumir o problema a: Qual a probabilidade de que existam $i,j$ distintos tais que $x_{i} = x_{j}$?.\\
	\vfill
	\item .Tendo $q = \Theta (2^{l / 2})$, a probabilidade é de aproximadamente $1/2$. No caso do aniversário, com $23$ pessoas na sala, a probabilidade de que $2$ façam aniversario no mesmo dia é maior que $1/2$. \\ 
	\vfill
	\end{itemize}
}

\frame{
  \frametitle{4.6.3 A Generic "Birthday" Attack}
  \begin{itemize}
	\item Considerando o tempo de se calcular $H$ constante, para uma função resistir a um ataque de rode em tempo $T$, o tamanho da mensagem digeridatem que ter ao menos $2\ log T$ bits. \\
	\vfill
	\item Pensando assintoticamente, não faz diferença se um ataque tenta $2^{l} + 1$ ou $2^{l/2}$ elementos, em ambos os casos se $l(n) = O(\log n)$ então os 2 ataques rodam em tempo polinomial, entretanto, se $l(n)$ super-logaritmico, então os dois ataques não são.
	\vfill
	\item Mas na prática o ataque de aniversário faz diferença. Para um chave de 128 bits é claramente inviavel de se calcular $2^{128}$ passos para se encontrar uma colisão. Entretanto $2^{64}$ ja é bem mais viavel, apesar de custoso.\\
	\vfill
	\end{itemize}
}

\frame{
  \frametitle{Improved birthday attacks}
  \begin{itemize}
	\item O maior problema do ataque de aniversário é a grande quantidade de memoria que ele precisa, assim como a falta de controle sobre os valores que colidem.\\
	\vfill
	\item É possivel fazer um ataque melhor usando uma quantidade de memoria constante.\\ 
	\vfill
	\item A ideia é pegar um valor incial randomico $x_{i}$  e para $ i > 0$ calcular os valores $x_{i} := H(x_{i - 1})$ e $x_{2i} := H(H(x_{2(i - 1)}))$.\\ 
	\vfill
	\item A cada passo $x_{i}$ e $x_{2i}$ são comparados; Se eles forem iguais, então $x_{i-1}$ e $H(x_{2(i - 1)})$ são uma colisão ( a não ser que aconteça deles serem iguais).
	\vfill
	\end{itemize}
}


\frame{
  \frametitle{4.6.4 The Merkle-Damg\aa rd Transform}
  \begin{itemize}
	\item Com essa metodologia é possivel converter qualquer função hash de tamanho fixo para uma de tamanho arbitrario, mantendo a propriedade de resistencia à colisão.\\
	\vfill
	\begin{block}{Contruction 4.13}
		Let $(Gen,h)$ be a fixed-length collision-resistant hash function for inputs of length $2l(n)$ and with putput length $l(n)$. Construct a variable-length hash function $(gen,H)$ as follows: \\
		\vfill
 		 \begin{itemize}
			\item $Gen:$ remais unchanged.\\
			\vfill
			\item $H:$ on input a key $s$ and a string $x \in \{0,1\}*$ of length $L < 2{l(n)}$, do the following ( set $l = l(n) in what follows$).\\ 
			\vfill
			\begin{enumerate}
				\item Set $B := \lceil \frac{L}{l} \rceil$ ( i.e., the number of blocks in $x$). Pad $x$ with zeroes so its length is a multiple of $l$. Parse the padded result as the sequence of $l$-bit blocks $ x_{1}, . . . , x_{B}$. Set $x_{B+1} :"= L$, where $l$ is encoded using exactly $l$ bits .\\
				\vfill
				\item Set $z_{0} := ^{l}$.\\
				\vfill
				\item For $i = 1, . . . , B + 1$, compute $z_{i} := h^{s}(z_{i-1}\|x_{i})$.\\
				\vfill
				\item Output $z_{B+1}$.\\
				\vfill
			\end{enumerate}
		\end{itemize}
	\end{block}
	\item $z_{0}$ pode ser trocado por qualquer constante. Tambem chamado de $IV$.\\
   \end{itemize}
}

\frame{
  \frametitle{The security on the Merkle-Damg\aa rd transform}
  \begin{itemize}
	\item A intuição diz que se duas strings diferentes, $x$ e $x'$ colidem em $H^{s}$ então em algum passo intermediario. Ou seja, valores $z{i-1}\|x_{i}$ e $z'_{i-1}\|x'_{i}$ no calculo de $H^{s}(x)$ e de $H^{s}(x')$ respectivamente tal que $h^{s}(z_{i-1}\|x_{i}) = h^{s}(z'_{i-1}\|x'_{i})$\\
	\vfill
	\begin{block}{Theorem 4.14}
		If $(gen,h)$ is a fixed-length collision-resistant hash function, then $(Gen,H)$ is a collision-resistant hash function.
	\end{block}
	\end{itemize}
}

\frame{
  \frametitle{The security on the Merkle-Damg\aa rd transform}
	\begin{block}{Proof}
		We show that for any $s$ a collision in $H^{s}$ yields a collision in $h^{s}$. Let $x$ and $x'$ be two different strings of respective lengths $L$ and $L'$ such that $H^{s}(x) = H^{s}(x')$. Let $x_{1}, . . . ,x_{B}$ be the $B$ blocks of the padded $x$, and let $x'_{1}, . . . , x'_{B'}$, be the $B'$ blocks of the padded $x'$. Recall that $x_{B+1} = L$ and $x'_{B+1} = L'$. There are two cases to consider:\\
	\vfill
	\end{block}
}
\frame{
  \frametitle{The security on the Merkle-Damg\aa rd transform}
	\begin{block}{Proof}
	\begin{enumerate}
		\item \textit{Case 1:} $L \neq L'$. In this case, the last step of the computation of $H^{s}$ is $z_{B+1} := h^{s}(z_{B}\|L)$ and the last step of the computation of $H^{s}(x')$ is $z'_{B'+ 1} := h^{s}(z'_{B'}\|L')$. Since $H^{s}(x) = H^{s}(x')$ it follows that $h^{s}(z_{B}\|L) = h^{s}(z'_{B'}\|L')$. However, $L \neq L'$ and so $z_{B}\|L$ and $z'_{B'}\|L'$ are two differente strings that collide for $h^{s}$.\\
		\vfill
		\item \textit{Case 2:} $L = L'$. Note this means that $B = B'$ and $x_{B+1} = x'_{B+1}$. Let $z_{i}$ and $z'_{i}$ be the intermediate hash values of $x$ and $x'$ during the computation of $H^{s}(x)$ and $H^{s}(x')$, respectively. Since $x \neq x'$ but $|x| =  |x'|$, there must exist at least one index $i$ (with $1 \leq i \leq B$) such that $x_{i} \neq x'_{i}$.Let $i* \leq B + 1$ be the \textit{highest} index for which it holds that $z_{i* - 1} \|x_{i*} \neq z'_{i* - 1}\| x'_{i* -1}\|x'_{i*}$. If $i* = B + 1$ then $z_{B}\|x_{B + 1}$ and $z'_{B}\|x'_{B+1}$ are two different strings that collide for $h^{s}$ because \\
		\vfill
		\begin{equation}
			h^{s}(z_{B}\|x_{B+1}) = z_{B+1} = H^{s}(x) = H^{s}(x') = z'_{B+1} = h^{s}(z'_{B}\|x'_{B+1})
		\end{equation}
	\end{enumerate}
	\end{block}
}

\frame{
  \frametitle{The security on the Merkle-Damg\aa rd transform}
	\begin{block}{Proof}
	\begin{itemize}
	\item  If $i* \leq B$, then maximality of $i*$ implies $z_{i*} = z'_{i*}$. Thus, once again, $z_{i* - 1} \| x_{i*}$ and $z'_{i* - 1} \| x'_{i*}$ are two different strings that collide for $h^{s}$.\\
	\vfill	
	\end{itemize}
	\end{block}
	 \begin{itemize}
		\item Segue que qualquer colisão na função hash $H^{s}$ rende uma colisão na função hash de tamanho fixo $h^{s}$.\\
	\end{itemize}
}

\frame{
  \frametitle{4.6.5 Collision-Resistant Hash Functions in Practice}
  \begin{itemize}
	\item Na prática funções hash resistentes a colisão não tem chave. Por tanto uma função é escolida e fixada. Alem, a noção de algoritmo de geração $Gen$ não é mais necessaria.\\
	\vfill
	\item Com isso não é possivel provar resistencia a colisão de funçoes usadas na prática. Entretanto isso não quer dizer que abolimos as provas completamente . \\
	\vfill
	\item Percebendo que é dificil encontar colisões num tempo rasoavel, então isso nos da uma garantia de segurança rasoavel.\\ 
	\vfill
	\end{itemize}
}
\frame{
  \frametitle{4.6.5 Collision-Resistant Hash Functions in Practice}
  \begin{itemize}
	\item Duas funções usadas na prática são o SHA-1 e o MD5 (apesar do MD5 já não ser mais seguro. Elas seriam funções de tamanho fixo que usam a transformada de Merkle-Damg\aa rd para aceitarem entradas de tamanho variado.\\
	\vfill
	\item O tamanho da saida do MD5 é 128 bits e do SHA-1 160 bits. Pelo tamanho maior do SHA-1, o ataque de aniversário nele se torna mais dificil: $\approx 2^{160/2} = 2^{80}$ contra $\approx 2^{128/2} = 2^{64}$ calculos de hash.\\
	\vfill
	\item Em 2004 um grupo de chineses apresentou um ataque inovador contra o MD5 e outra funções hash relacionadas. Em 2005 eles apresentaram ataques teoricos contra o SHA-1. Seu ataque requer somente $2^{69}$ calculo de hashs. Como não foram encontradas colisões explicitas ao SHA-1, esse número ainda é inalcançável.\\ 
	\vfill
	\item Esses ataque motivaram substituições por funções hash mais fortes, com saidas maiores. São a familia SHA-2 e incluem funções de 256 e 512bits de saida.\\
	\vfill
  \end{itemize}
}

